1852A - Ntarsis' Set - CodeForces Solution

#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ull unsigned long long
#define fastio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define ts to_string
#define ff first
#define ss second
#define pb push_back
#define nl "\n"
#define MOD 1000000007
#define mod 998244353
#define inf 1e18
#define All(v) v.begin(), v.end()
#define set_bits __builtin_popcountll
#define prDouble(x) cout << fixed << setprecision(10) << x <<nl
#define yes cout<<"YES"<<nl
#define no cout<<"NO"<<nl
#define minus cout<<"-1"<<nl
#define r(x) return void(x)
#define c(x) cout<<x<<nl
using namespace std;
using namespace __gnu_pbds;
const ll N=200005;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds; // find_by_order(), order_of_key()
void solve(){
    ll n, k; cin>>n>>k;
    vector<ll> v(n);
    for (ll i=0; i<n; i++) cin>>v[i];
    if (v[0]!=1) r(c(1));

    // Binary Search
    // For mid, check how many number of days required to remove all elements from [1, mid].
    // If the days required is greater than k, then ans can be mid or less than mid. Otherwise, ans is greater than mid.
    
    ll low=1, high=inf, mid, ans;
    while (low <= high){
        mid=low+(high-low)/2;
        ll curr=mid;
        // Iterate in v from reverse, and find for how many days, the position v[i] will remove the elements from [1, curr].
        ll totDays=0;
        // cout<<mid<<endl;
        for (ll i=n-1; i>=0; i--){
            if (v[i]>curr) continue;
            // curr - (days*(i+1)) >= v[i], because each time we remove (i+1) elements from [1, curr].
            ll days = (curr-v[i])/(i+1);
            days++;
            totDays+=days;
            curr-=days*(i+1);
        }
        if (totDays > k) ans=mid, high=mid-1;
        else low=mid+1;
    }   
    c(ans);
}           
int main(){
#ifndef ONLINE_JUDGE                                                                                                                                
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    freopen("error.txt", "w", stderr);
#endif  
    fastio(); 
    ll t=1; cin>>t;
    while(t--)
        solve();
    return 0;
}